遅延ストリームに対する表現可能関手(Representable) を実装してみた

Category theory for Programmerで紹介されていた遅延ストリームに対するRepresentableをScalaで実装しました。

#Scala

佐々木一洋

2022.10.28

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

はじめに

CTfP(Category Theory for Programmer) の表現可能関手の節でStreamに対するRepresentableの実装が紹介されていたのでいつものようにScalaで書き直してみました。

catsにおけるRepresentable

catsでの定義は以下の通りです。

trait Representable[F[_]] extends Serializable { self =>
  def F: Functor[F]
  type Representation
  def index[A](f: F[A]): Representation => A
  def tabulate[A](f: Representation => A): F[A]
}

tabulateがホム関手C(A,_)から関手Fの自然変換、indexが関手Fからホム関手(C(A, _)の自然変換にそれぞれ対応します。

Stream

とりあえずStreamとそのFunctorを以下のように実装しておきます。

final class Stream[A] private (_a:A, _as: => Stream[A]):
    val a = _a
    lazy val as = _as
object Stream:
    def apply[A](a:A, as: => Stream[A]) = new Stream(a, as)
    given show[A]: Show[Stream[A]] = Show.show(s => s"Stream(${s.a},as)")
    given functor: Functor[Stream] = new Functor[Stream] :
      override def map[A, B](fa: Stream[A])(f: A => B): Stream[B] = Stream(f(fa.a), map(fa.as)(f))

Representable

CTfPでの実装と同様にRepresentationにIntを選びます。AuxでRepresentationを明示する必要があります。


given repr: Representable.Aux[Stream, Int] = new Representable[Stream] :
	override def F: Functor[Stream] = summon[Functor[Stream]]
  override type Representation = Int
  override def index[A](f: Stream[A]): Int => A = {
	  case 0 => f.a
    case idx => index(f.as)(idx - 1)
  }
  override def tabulate[A](f: Int => A): Stream[A] = Stream(f(0), tabulate(f compose(_+1)))

実行してみる

特に面白みはないんですがindexの方でストリームを走査して100を取り出せたことがわかります。

val rep = summon[Representable.Aux[Stream, Int]]
println(rep.tabulate(identity).show) //Stream(0,as)
println(rep.index(rep.tabulate(identity))(100)) //100

catsで見つけた実装

ついでにcatsで見つけたいくつかの実装を眺めてみます。

Function1

下記はFunction1での実装の抜粋です。関手 (E → A) はホム関手 C(E, A)と同じくE → A の射なのでtabulateとindexの実装は受け取った関数をそのまま返すだけになっています。

implicit def catsStdRepresentableForFunction1[E](implicit EF: Functor[E => *]): Representable.Aux[E => *, E] =
    new Representable[E => *] {
      override type Representation = E
      override val F: Functor[E => *] = EF
      override def tabulate[A](f: E => A): E => A = f
      override def index[A](f: E => A): E => A = f
    }

Kleisli

下記はKleisliでの実装の抜粋です。型が多くてややこしいのですが、ホム関手を C((E, R), _) 、KleisliをA → M A に写す関手だと思えば読めました。RepresentiveがRではなく(E, R)とタプルになっているのはindexの実装においてf: Kleisli[M, E, A]からAを取り出すために必要なのはわかるのですが圏論においてどういった意味になるのかがわかりませんでした。

implicit def catsDataRepresentableForKleisli[M[_], R, E](implicit
    R: Representable.Aux[M, R],
    FK: Functor[Kleisli[M, E, *]]
  ): Representable.Aux[Kleisli[M, E, *], (E, R)] =
    new Representable[Kleisli[M, E, *]] {
      override type Representation = (E, R)
      override val F: Functor[Kleisli[M, E, *]] = FK
      def index[A](f: Kleisli[M, E, A]): Representation => A = { case (e, r) =>
        R.index(f.run(e))(r)
      }
      def tabulate[A](f: Representation => A): Kleisli[M, E, A] =
        Kleisli[M, E, A](e => R.tabulate(r => f((e, r))))
    }